JZ3 从尾到头打印链表

链接：https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035

最 low 的方法就是递归，因为有额外的空间复杂度，所以不使用

第一次解：手动逆序

    public  ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
        if (listNode == null) return new ArrayList<Integer>();
        // 逆序
        ListNode cur = null;
        ListNode pre = listNode;
        // 三指针法
        while (pre != null) {
            ListNode temp = pre.next;
            pre.next = cur;
            cur = pre;
            pre = temp;
        }
        
        ArrayList<Integer> result = new ArrayList<>();
        while (cur != null) {
            result.add(cur.val);
            cur = cur.next;
        }
        
        return result;
    }  

第二次解：头插法

最优的方法，利用 LinkedList 头插法

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Collections;

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if (listNode == null) return new ArrayList<Integer>();
        // 逆序
        LinkedList<Integer> list = new LinkedList<>();
        list.add(listNode.val);
        listNode = listNode.next;
        while(listNode != null) {
             list.add(0,listNode.val);
             listNode = listNode.next;
        }
        return new ArrayList(list);
    }
}

不要使用 ArrayList 头插，否则时间复杂度就成 $O(n^2)$ 了

Go 解法

func printListFromTailToHead(head *ListNode) []int {
    if head == nil {
        return []int{}
    }
    result := make([]int,10000)
    i := 9999
    for {
        result[i] = head.Val
        head = head.Next
        if head != nil {
            i--
        } else {
            break
        }
    }
    return result[i:]
}

另一种形式的头插法

23-5-23

简简单单的头插法

耗时：4:48

func printListFromTailToHead(head *ListNode) []int {
    var res []int
    for head != nil {
        res = append([]int{head.Val}, res...)
        head = head.Next
    }
    return res
}